package common;

import java.util.Arrays;

public class ArrayTrie {
    private int m = 20;
    public int[][] tree = new int[m][26];
    public int[] pass = new int[m];
    public int[] end = new int[m];
    private int cnt = 0;

    public ArrayTrie() {
        this.cnt = 1;
    }

    public void printTitle() {
        System.out.print("  [ ");
        for (int i = 0; i < 25; i++) {
            System.out.print((char) (97 + i) + "  ");
        }
        System.out.print("  ]");
        System.out.println();
    }

    public void insert(String world) {
        int cur = 1;
        pass[cur]++;
        for (int i = 0; i < world.length(); i++) {
            int path = world.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
            pass[cur]++;
        }
        end[cur]++;
    }

    public int search(String world) {
        int cur = 1;
        for (int i = 0; i < world.length(); i++) {
            int path = world.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                return 0;
            }
            cur = tree[cur][path];
        }
        return end[cur];
    }

    public int prefixNumber(String world) {
        int cur = 1;
        for (int i = 0; i < world.length(); i++) {
            int path = world.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                return 0;
            }
            cur = tree[cur][path];
        }
        return pass[cur];
    }

    public void delete(String world) {
        int cur = 1;
        pass[cur]--;
        for (int i = 0; i < world.length(); i++) {
            int path = world.charAt(i) - 'a';
            if (--pass[tree[cur][path]] == 0) {
                tree[cur][path] = 0;
                return;
            }
            cur = tree[cur][path];
        }
        end[cur]--;
    }

    public void clear() {
        for (int i = 0; i < cnt; i++) {
            Arrays.fill(tree[i], 0);
            end[i] = 0;
            pass[i] = 0;
        }
    }
}
